package heap;

import java.util.Arrays;

/**
 * @author zhangboyu
 */
public class MaxHeap<Key extends Comparable<Key>> {
    //since binary heap is a full binary tree, it is efficient we use an array to retain it
    private Key[] pq;
    private int size;


    public MaxHeap(int cap) {
        pq = (Key[]) new Comparable[cap + 1];
    }

    public Key getMax() {
        return pq[1];
    }

    public Key poll() {
        Key max = pq[1];
        exchange(1, size);
        size--;
        sink(1);
        return max;
    }
    public void add(Key e){
        size++;
        if(size >= pq.length){
            grow();
        }
        pq[size] = e;
        swim(size);
    }
    private void grow() {
        int oldCapacity = pq.length;
        // Double size if small; else grow by 50%
        int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                (oldCapacity + 2) :
                (oldCapacity >> 1));
        pq = Arrays.copyOf(pq, newCapacity);
    }

    private void swim(int k) {
        while (k > 1 && less(parent(k), k)) {
            exchange(parent(k), k);
            k = parent(k);
        }
    }

    private void sink(int k) {
        while (left(k) <= size) {
            int larger = left(k);
            if (right(k) <= size && less(larger, right(k))) {
                larger = right(k);
            }
            if (less(k, larger)) {
                exchange(k, larger);
            } else {
                break;
            }
            k = larger;
        }
    }

    private void exchange(int i, int j) {
        Key tmp = pq[i];
        pq[i] = pq[j];
        pq[j] = tmp;
    }

    private boolean less(int i, int j) {
        return pq[i].compareTo(pq[j]) < 0;
    }

    private int parent(int k) {
        return k / 2;
    }

    private int left(int k) {
        return k * 2;
    }

    private int right(int k) {
        return k * 2 + 1;
    }
    public boolean isEmpty(){
        return size == 0;
    }

    public static void main(String[] args) {
//        int[] testArr =  new int[]{5,15,2,4,7,1,3};
//        MaxHeap<Integer> heap =  new MaxHeap<>(4);
//        for(int i: testArr){
//            heap.add(i);
//        }
//        while(!heap.isEmpty()){
//            System.out.println(heap.poll());
//        }
        int i = 5;
        int j  = 6;
        i = i^j;
        j = j^i;
        i = j^i;

        System.out.println(j);
        System.out.println(i);

    }
}
